import java.util.*;
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Test {
    /*
    题目 1：链表中环的入口节点
     */
    // fast 走过的节点数是 slow 走过的两倍
    // f = 2s
    //如果存在环，环前的节点数为 a ，而整个环的节点数为 b
    // 当 fast 和 slow 两者相遇的时候
    // f = s + nb
    //由此可得 s = nb
    //而再进一步去想，发现抵达环入口处经过的节点数为 a + nb
    //也就是说，相遇处的 slow 指针再走 a 步就可以到达环入口处！！
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null || pHead.next == null){
            return null;
        }

        ListNode fast = pHead;
        ListNode slow = pHead;

        while(fast != null && fast.next != null ){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                break;
            }
        }

        //fast == slow 意味着有环！
        if(fast == slow){
            fast = pHead;

            while(fast != slow){
                fast = fast.next;
                slow = slow.next;
            }
        }else{
            return null;
        }

        return slow;
    }

    /*
    题目 2：两个链表的第一个公共节点
     */
    //两个有公共节点的链表，可能长度不一
    //便让 两个指针 l1 和 l2 分别遍历一遍 pHead1 以及 pHead2 ，遇到 null 了，
    //再交换遍历，l1 和 l2 分别遍历一遍 pHead2 以及 pHead1，如此一来遍历的长度便是一样的
    //这样就可以找到公共节点
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1;
        ListNode l2 = pHead2;

        while(l1 != l2){
            l1 = (l1 == null)?pHead2:l1.next;
            l2 = (l2 == null)?pHead1:l2.next;
        }
        return l1;
    }

    /*
    题目 3 : 链表相加
     */
    //思路：使用两个栈将 链表节点 依次装入
    //依次弹出，相加的结果以及进位放入新的链表节点，使用尾插法！！
    public ListNode addInList (ListNode head1, ListNode head2) {
        LinkedList<ListNode> stack1 = new LinkedList<>();
        LinkedList<ListNode> stack2 = new LinkedList<>();

        addNode(head1, stack1);
        addNode(head2, stack2);

        //记录下进位的数字
        int carry = 0;

        ListNode head = null;

        while(!stack1.isEmpty() || !stack2.isEmpty() || carry != 0){
            int x = (stack1.isEmpty()) ? 0 : stack1.pop().val;
            int y = (stack2.isEmpty()) ? 0 : stack2.pop().val;

            int sum = x + y + carry;
            carry = sum / 10;

            ListNode node = new ListNode(sum % 10);

            node.next = head;
            head = node;
        }
        return head;
    }

    public void addNode(ListNode head, LinkedList<ListNode> stack){
        ListNode cur = head;
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }
    }


}
